\rsec{Coleta de Dados}

A aplicação dos métodos de classificação acima depende dos dados iniciais que
representam o conjunto de páginas a ser analisado. Para obtê-los, é necessário
percorrer as páginas e descobrir quais são as URLs que representam links válidos
(que apontam para outras páginas, e não para algum tipo de arquivo, por
exemplo). Para isso, é utilizado uma espécie de ``robô'', conhecido como
\textit{crawler}, que percorre as páginas automaticamente e obtém a estrutura de
links desejada.

O \textit{crawler} possui a função de acessar as páginas e baixá-las, mas o
importante nesse contexto é identificar os links que uma página contém. Para
isso, foi utilizado um \textit{parser}, que tem como objetivo filtrar todo o
conteúdo de um código fonte em busca de possíveis links.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\rssec{Crawler}

A implementação do crawler que foi feita tem um aspecto diferente dos demais:
ele limita os links válidos de acordo com o domínio oferecido. A ideia principal
é verificar a estrutura de páginas sob um determinado domínio, por exemplo, o
domínio \url{www.ime.usp.br}. Inicialmente, a página principal do instituto será
analisada pelo parser e então avaliaremos todos as links contidos nela. Com essa
mudança, conseguimos filtrar algumas páginas cuja análise não é interessante,
como \url{www.usp.br}, pois esta se encontra fora do domínio
\texttt{www.ime.usp.br}. Por outro lado a página do Departamento de Ciência da
Computação (\url{www.ime.usp.br/dcc}) será guardada para posterior análise de
seus links.

O crawler recebe dois argumentos, sendo um arquivo com um domínio e um inteiro
que limita o número de páginas que serão analisadas.

O algoritmo é baseado na seguinte ideia:

\begin{itemize}

\item Lista de URLs\\
Pega-se a próxima URL da lista para análise. Esta lista de URLs contém apenas
as páginas que foram encontradas durante o processo de busca e ainda não foram
analisadas.

\item Download\\
Uma vez com a nova URL em mãos, o crawler, por meio da biblioteca cURL, acessa
esta URL e, se possível, faz o download do código fonte dela.

\item Análise\\
O código fonte é passado para o parser, para que este analise a página,
procurando os links que estão hierarquicamente sob o domínio dado. 
Uma vez terminada a análise, o parser devolve uma lista com todas as URLs
encontradas.

\item Atualização\\
O crawler recebe a lista do parser e atualiza a lista de URLs, com o cuidado de
não colocar neste lista um endereço que está ou já esteve nela. Isso é feio por
meio de uma função de espalhamento que controla as URLs já encontradas.

\item Término\\
O processo termina quando o crawler chega ao número máximo de páginas passado
como argumento ou se a fila terminar antes deste número, caso contrário,
segue-se pegando a próxima URL da fila.

\end{itemize}

Utilizando-se de uma perspectiva diferente, podemos entender o crawler como uma
espécie de busca em largura pelos vértices de um grafo, no caso o grafo da web.
A página em análise corresponde ao vértice em que o algoritmo se encontra e as
páginas com URL válidas correspondem aos vértices vizinhos. A lista de URLs que
o crawler acessa nada mais é do que a fila que existe em um algoritmo de busca
em largura tradicional.

A tecnologia que utilizamos para integrar a linguagem C à internet foi uma
biblioteca chamada cURL (\url{curl.haxx.se/libcurl}), que nos permitiu acessar e
obter o código fonte de uma página na web. Para que a execução do crawler seja
correta, é necessário que haja conexão com a internet.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\rssec{Parser}

\begin{verbatim}
<html>
  <head>
    <title>Katague's page</title>
  </head>
  <body>
    "By knowing things that exist, you can know that which does not exist."
    - Miyamoto Musashi

    <a href="1.html">1</a>
  </body>
</html>
\end{verbatim}

O trecho acima ilustra um exemplo simplificado de código fonte de uma página
html. Para conseguirmos extrair os links de uma página, foi implementado um
parser em linguagem C. Um parser é um programa que realiza uma análise sintática
em uma sequência de entrada, onde no nosso caso temos o código fonte de uma
página (html, htm, php). Procuramos ocorrências da tag
\texttt{<a href=``...''>}.

\textit{``The <a> tag defines a hyperlink, which is used to link from one page
to another.''} - \url{www.w3schools.com}

O parser manipula o arquivo que contém o código fonte da página que está sendo
analisada. Além de extrair os links das páginas, ele também faz a análise da
URL, para conferir se esta pertence ao domínio ou não, ou também se não é um
tipo de arquivo. Além disso, o parser também é responsável pela extração do
título da página, identificado pelas tags \texttt{<title>} e \texttt{</title>}.

Inicialmente, é necessário definir no parser sob qual domínio as páginas serão
analisadas. Antes de encaminhar qualquer página para análise, o crawler deve
chamar a função \texttt{parser\_init(char*)} que recebe a string correspondente
ao domínio. Em vários momentos o parser manipula as URLs para um formato que
seja mais conveniente trabalhar. Se o domínio, por exemplo, for encaminhado pelo
crawler como \texttt{"http://www.ime.usp.br/"}, o parser ignora o trecho
\texttt{"http://"} e a \texttt{"/"} final, transformando-o em
\texttt{"www.ime.usp.br"}.

Após as configurações iniciais, o crawler pode fazer a chamada da função
principal do parser, \texttt{parse(char*, char*, char*)}, onde o primeiro
argumento é o nome do arquivo contendo o código fonte a ser analisado, o segundo
é o nome do arquivo onde o parser escreverá os links válidos, e o terceiro é a
URL global correspondente ao código fonte. Nesse momento, o parser começa a
procurar os links da página, e cada um deles passa por um filtro, que determina
se a URL do link aponta para outra página dentro do domínio ou não.

O primeiro filtro consiste em procurar na URL extensões de arquivos não
relacionados a formatos web, como \texttt{jpg}, \texttt{mp3}, entre outros. O
parser está programado para filtrar cerca de 80 tipos de formatos de arquivos
diferentes. Após essa verificação, ele procura por padrões como \texttt{mailto:}
ou \texttt{file:}. Se o parser encontrar algum desses padrões, a URL é
descartada.

Entretanto, a URL pode conter caracteres em hexadecimal, cujo número corresponde
ao caracter em ASCII. Se a URL não foi descartada até aqui, ocorre a conversão
desses caracteres para o padrão usado pela linguagem C, por exemplo, se no meio
da URL houver uma ocorrência \texttt{"/\%7Ecoelho"}, o parser fará o ajuste para
\texttt{"/\textasciitilde coelho"}.

Alguns caracteres especiais podem aparecer na URL \cite{rfc3986}. Por exemplo,
\texttt{'\#'} representa uma âncora dentro de uma página, isto significa que
\texttt{pt.wikipedia.org/wiki/USP} e
\texttt{pt.wikipedia.org/wiki/USP\#Estrutura} apontam para a mesma página, e
\texttt{'?'} representa os parâmetros de uma busca em determinada URL. O parser
identifica estes caracteres especiais e os elimina, junto com o seus parâmetros,
deixando a URL mais ``limpa''.

O fato de duas URLs distintas poderem apontar para uma mesma página foi uma das
maiores dificuldades a ser solucionada. Houve uma tentativa de reduzir os
efeitos desse problema, mas não é correto afirmar que o parser implementado é
completamente imune a ele. Uma das situações é a ocorrência de
\texttt{"index.html"} na URL. Caso ocorra, o parser o retira da URL.

Passado por todos esses filtros, o parser procura pelo padrão do domínio na URL.
Por isso, ao ajustar o domínio no começo do processo (em \texttt{set\_domain()})
fizemos com que o \texttt{http://} e a \texttt{'/'} final não fossem incluídas
no domínio. Caso o domínio ocorra na URL, temos uma URL correspondente a um link
válido. Caso contrário, procuramos a ocorrência de \texttt{http://} e alguns dos
domínios mais usados na internet, como \texttt{.com}, \texttt{.net},
\texttt{.org}, e caso alguma dessas ocorrências for positiva, sabemos que a URL
é global, e se o domínio não ocorre nela, então não é válida.

Se a URL chegou até esse ponto, pode-se afirmar que ela é local. A presença
destas gera muitos casos de tratamento, e cabe ao parser fazer a conversão para
as URLs globais, e é por isso que existem variáveis, \texttt{domain},
\texttt{actual} e \texttt{http\_domain} (esta última guarda a raiz http de onde
se encontra o domínio) que guardam algumas URLs especiais. Para exemplificar, se
o domínio escolhido é \texttt{www.ime.usp.br/\textasciitilde cef}, e a página
atual que está sendo analisada pelo parser é
\texttt{www.ime.usp.br/\textasciitilde cef/mac499-10/}, temos:

\begin{itemize}

\item \texttt{domain = "www.ime.usp.br/\textasciitilde cef"}
\item \texttt{http\_domain = "www.ime.usp.br"}
\item \texttt{actual\_url = "www.ime.usp.br/\textasciitilde cef/mac499-10/"}

\end{itemize}

Existe um caso especial de tratamento, que são as URLs começadas com \texttt{/},
como \texttt{``/\textasciitilde cef''}. Uma URL que começa com \texttt{/} faz
referência ao diretório raiz http. No caso, o parser concatena
\texttt{http\_domain} com \texttt{"/\textasciitilde cef"}, gerando a URL global
\texttt{www.ime.usp.br/\textasciitilde cef}

As demais URLs podem ter ocorrências de \texttt{./} ou \texttt{../}, como
\texttt{"./monografias/"} ou \texttt{"../orient.html"}, ou mesmo simplesmente
\texttt{"plagio.html"}. Nestes casos, o parser monta a URL global concatenando
\texttt{actual\_url} com a URL encontrada. Ao concatenar, teremos como URL
\texttt{"www.ime.usp.br/\textasciitilde cef/mac499-10/../orient.html"} por
exemplo. O parser trata a URL e a transforma em
\texttt{"www.ime.usp.br/\textasciitilde cef/orient.html"}. O parser também trata
um caso especial, onde no diretório raiz \texttt{../} recai no próprio diretório
raiz.

Essa padronização das URLs é necessária, porque é essencial que o crawler
consiga distinguir quais páginas já foram analisadas e quais não foram.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\rssec{Hash}

Durante sua execução, o crawler eventualmente vai encontrar uma página que já
foi acessada, logo seria conveniente se houvesse uma maneira de distinguir quais
páginas já foram visitadas, algo análogo a pintar os vértices já visitados em
uma busca.
Para isso, utilizamos uma função de espalhamento (\textit{hash}), adaptada de
um código escrito por Donald Knuth, que nos foi fornecido pelo Prof. Coelho.
Nesta função de espalhamento a chave escolhida para distinguir as páginas é a
URL.

Entretanto, duas cadeias de caracteres distintas podem apontar para a mesma
página. O parser trata as URLs locais, mas não filtra o \texttt{http://} e a
\texttt{/} final ao devolvê-las para o crawler. Ao aplicar a função de
espalhamento numa URL, o programa verifica se estes padrões aparecem na URL e os
filtram, para tentar garantir a unicidade de cada página.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\rssec{Arquivos de Saída}

No final do processo, o crawler disponibiliza dois arquivos de saída:

\begin{itemize}

\item nodes.txt\\
Neste arquivo temos a lista com as páginas analisadas, de modo que cada página 
gera uma entrada da forma:

\begin{verbatim}
12
http://www.ime.usp.br/~coelho/geocomp2002
MAC0331 / MAC5747 Geometria Computacional
16
\end{verbatim}

Em que cada linha representa, respectivamente: índice, URL, título e número de
links.

É importante ressaltar que o número de links se restringe apenas às páginas que
se encontram no domínio. Além disso, se houver mais de um link para uma mesma
página, apenas um deles será considerado.

\item adj\_list.txt\\
Neste arquivo, temos a lista de adjacência do grafo construído pelo crawler, no
formato exato para que sirva de entrada para o programa que calcula o PageRank e
o HITS.

\end{itemize}


